package string;

// reference: http://en.wikipedia.org/wiki/Levenshtein_distance
// timing complexity: O(n * m) where n is length of first string 
// and m is length of second string
public class EditDistance {

	/**
	 * Returns edit distance to convert str1 into str2
	 * */
	public static int editDistance(String str1, String str2){
		
		int len1 = str1.length();
		int len2 = str2.length();
		
		int[][] matrix = new int[len1 + 1][len2 + 1]; // by default initialized to zero in java
		
		// edit distance to convert a string of i chars to empty string
		for(int i = 0; i <= len1; i++){
			matrix[i][0] = i;
		}

		// edit distance to convert an empty string to an string of j chars
		for(int j = 0; j <= len2; j++){
			matrix[0][j] = j;
		}
		
		// calculate edit distance
		for(int i = 0; i < len1; i++){
			for(int j = 0; j < len2; j++){

				if(str1.charAt(i) == str2.charAt(j)){
					matrix[i+1][j+1] = matrix[i][j];
				}else{
					matrix[i+1][j+1] = (int)Math.min(matrix[i][j] + 1 , (int)Math.min(matrix[i][j+1] + 1, matrix[i+1][j] + 1));
				}
			}
		}
		
		// retun edit distance of str1 and str2
		return matrix[len1][len2];
	}
	
	
	public static void main(String[] args){
		System.out.println("editDistance(\"bob\", \"bob\"): "+editDistance("bob", "bob")); // ans: 0
		System.out.println("editDistance(\"bomy\", \"bob\"): "+editDistance("bomy", "bob")); // ans: 2
		System.out.println("editDistance(\"sunday\", \"saturday\"): "+editDistance("sunday", "saturday")); // ans: 3
		System.out.println("editDistance(\"sitting\", \"kitten\"): "+editDistance("sitting", "kitten")); // ans: 3
	}
}
